package com.sheng.leetcode.year2025.month09.day01;

import org.junit.Test;

import java.util.PriorityQueue;

/**
 * @author by ls
 * @date 2025/9/16
 * <p>
 * 1792. 最大平均通过率<p>
 * <p>
 * 一所学校里有一些班级，每个班级里有一些学生，现在每个班都会进行一场期末考试。<p>
 * 给你一个二维数组 classes ，<p>
 * 其中 classes[i] = [passi, totali] ，表示你提前知道了第 i 个班级总共有 totali 个学生，<p>
 * 其中只有 passi 个学生可以通过考试。<p>
 * 给你一个整数 extraStudents ，表示额外有 extraStudents 个聪明的学生，<p>
 * 他们 一定 能通过任何班级的期末考。你需要给这 extraStudents 个学生每人都安排一个班级，使得 所有 班级的 平均 通过率 最大 。<p>
 * 一个班级的 通过率 等于这个班级通过考试的学生人数除以这个班级的总人数。平均通过率 是所有班级的通过率之和除以班级数目。<p>
 * 请你返回在安排这 extraStudents 个学生去对应班级后的 最大 平均通过率。与标准答案误差范围在 10^-5 以内的结果都会视为正确结果。<p>
 * <p>
 * 示例 1：<p>
 * 输入：classes = [[1,2],[3,5],[2,2]], extraStudents = 2<p>
 * 输出：0.78333<p>
 * 解释：你可以将额外的两个学生都安排到第一个班级，平均通过率为 (3/4 + 3/5 + 2/2) / 3 = 0.78333 。<p>
 * <p>
 * 示例 2：<p>
 * 输入：classes = [[2,4],[3,9],[4,5],[2,10]], extraStudents = 4<p>
 * 输出：0.53485<p>
 * <p>
 * 提示：<p>
 * 1 <= classes.length <= 10^5<p>
 * classes[i].length == 2<p>
 * 1 <= passi <= totali <= 10^5<p>
 * 1 <= extraStudents <= 10^5<p>
 */
public class LeetCode1792 {

    @Test
    public void test() {
//        int[][] classes = {{1, 2}, {3, 5}, {2, 2}};
//        int extraStudents = 2;
        // 36 * 5 = 180
        // 120 + 60 + 144 + 60  180
        int[][] classes = {{2, 4}, {3, 9}, {4, 5}, {2, 10}};
        int extraStudents = 4;
        System.out.println(new Solution().maxAverageRatio(classes, extraStudents));
    }
}

class Solution {
    public double maxAverageRatio(int[][] classes, int extraStudents) {
        // classes[i] = [passi, totali] ，表示第 i 个班级总共有 totali 个学生，其中只有 passi 个学生可以通过考试
        // 找出数组中 passi / totali，分子和分母各加 1 之后提升最大的
        // 优先队列，用来存储提升率，按照提升率从大到小排序
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Double.compare(increaseRate(b), increaseRate(a)));

        // 初始化优先队列
        for (int[] cls : classes) {
            pq.offer(cls);
        }

        // 分配学生
        while (extraStudents > 0) {
            int[] bestClass = pq.poll();
            // 增加一个通过学生
            bestClass[0]++;
            // 增加一个总学生
            bestClass[1]++;
            // 重新加入队列
            pq.offer(bestClass);
            extraStudents--;
        }

        // 计算结果
        double totalRatio = 0;
        for (int[] cls : classes) {
            totalRatio += (double) cls[0] / cls[1];
        }

        return totalRatio / classes.length;
    }

    /**
     * 计算当前班级的提升率增量
     *
     * @param cls
     * @return
     */
    private double increaseRate(int[] cls) {
        double originalRate = (double) cls[0] / cls[1];
        double newRate = (double) (cls[0] + 1) / (cls[1] + 1);
        return newRate - originalRate;
    }
}
